/*
 * (C) 2012	Sheng Yi
 * heap_sort --- O(NlogN)
 * sometimes when you want to select the bigget K elements in a arrary
 * heap sort may be helpfull
 */
#include <stdio.h>

#define	left(i)		((i) << 1)		// find left child of node i
#define right(i)	(((i) << 1) + 1) 	// find right child of node i
#define	parent(i)	((i) >> 1)		// find parent

// mainly operation is to keep the max of min heap
void keep_heap(int a[], int len, int k);
void build_heap(int a[], int len);
void heap_sort(int a[], int len);


int main()
{
	int a[10] = {2, 5, 3, 12, 78, 1, 4, 2, 7, 10};
	int i;
	for (i = 0; i < 10; i++)
		printf("%d ", a[i]);
	printf("\n");

	heap_sort(a, 10);

	for (i = 0; i < 10; i++)
		printf("%d ", a[i]);
	printf("\n");

	return 0;
}

// when the kth node was modified, the heap may be broken
// we should fix it
// assuption that all other nodes are good heap
void keep_heap(int a[], int len, int k)
{
	// the node just will delive down
	// judge if the leaf
	if (left(k) <= len)
	{
		int l = left(k);
		int r = right(k);
		int pos = k;
		// select the min value in parent and it's child(children)
		if (a[l - 1] < a[pos - 1]) 
			pos = l;
		if (r <= len && a[r - 1] < a[pos - 1])
			pos = r;

		// change the minimal node with parent
		if (pos != k)
		{
			int temp = a[pos - 1];
			a[pos - 1] = a[k - 1];
			a[k - 1] = temp;

			// recursion to keep heap
			// turn node pos
			keep_heap(a, len, pos);
		}
	}
}

void build_heap(int a[], int len)
{
	int i;
	// from the last node who has child
	// so when in high level, the lower level was heap
	for (i = len / 2; i > 0; i--)
		keep_heap(a, len, i);
}

void heap_sort(int a[], int len)
{
	int i;
	// build heap first
	build_heap(a, len);

	// desending
	// put the top of heap to the last
	// then reduce the heap length
	for (i = len; i > 1; i--)
	{
		// swap
		int temp = a[0];
		a[0] = a[i - 1];
		a[i - 1] = temp;

		// keep heap
		keep_heap(a, i - 1, 1);
	}
	
}
